package algorithms.leaning.class20;

import common.util.MyUtil;

/**
 * 请同学们自行搜索或者想象一个象棋的棋盘，
 * 然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置
 * 那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域
 * 给你三个 参数 x，y，k
 * 返回“马”从(0,0)位置出发，必须走k步
 * 最后落在(x,y)上的方法数有多少种?
 *
 * @author guichang
 * @date 2021/6/21
 */

@SuppressWarnings("all")
public class Code2_动态规划_马走日 {
    // 横坐标 0~9 纵坐标 0~8

    public static void main(String[] args) {
        int x = 7, y = 7, k = 14;
        long start1 = System.currentTimeMillis();
        MyUtil.print(ways(x, y, k));
        MyUtil.printf("耗时：{}", System.currentTimeMillis() - start1);
        long start2 = System.currentTimeMillis();
        MyUtil.print(waysDp(x, y, k));
        MyUtil.printf("耗时：{}", System.currentTimeMillis() - start2);
    }

    public static int ways(int x, int y, int k) {
        if (x < 0 || x > 9 || y < 0 || y > 8 || k < 1) {
            return -1;
        }
        // 八个方向
        int[][] pathArray = {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}};
        return process(0, 0, x, y, k, pathArray);
    }

    /**
     * 从[i,j]走到[x,y]还剩rest步
     */
    private static int process(int i, int j, int x, int y, int rest, int[][] pathArray) {
        // 越界
        if (i < 0 || i > 9 || j < 0 || j > 8) {
            return 0;
        }
        // 没次数了
        if (rest == 0) {
            return (i == x && j == y) ? 1 : 0;
        }

        // 还有步数可以跳
        int ways = 0;
        for (int[] path : pathArray) {
            ways += process(i + path[0], j + path[1], x, y, rest - 1, pathArray);
        }
        return ways;
    }

    public static int waysDp(int x, int y, int k) {
        if (x < 0 || x > 9 || y < 0 || y > 8 || k < 1) {
            return -1;
        }
        // 八个方向
        int[][] pathArray = {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}};
        int[][][] dp = new int[10][9][k + 1];
        dp[x][y][0] = 1;
        // 整体z坐标方向，内部方向随意
        for (int rest = 1; rest <= k; rest++) {
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < 9; j++) {
                    for (int[] path : pathArray) {
                        dp[i][j][rest] += getDp(dp, i + path[0], j + path[1], rest - 1);
                    }
                }
            }
        }
        return dp[0][0][k];
    }

    /**
     * 防止越界
     */
    private static int getDp(int[][][] dp, int i, int j, int rest) {
        if (i < 0 || i > 9 || j < 0 || j > 8) {
            return 0;
        }
        return dp[i][j][rest];
    }

}